package com.github.kezhenxu94.playground.java.sorting;

public class QuickSort {

	public void sort(int[] array, int from, int to) {
		if (from < to) {
			int sortedIndex = partition(array, from, to);
			sort(array, from, sortedIndex - 1);
			sort(array, sortedIndex + 1, to);
		}
	}

	private int partition(int[] array, int from, int to) {
		int pivot = array[from];
		int lastSmallerThenPivot = to;
		while (lastSmallerThenPivot > from && array[lastSmallerThenPivot] >= pivot)
			lastSmallerThenPivot--;
		for (int i = from + 1; i < lastSmallerThenPivot; i++)
			if (array[i] >= pivot) {
				ArrayUtil.swap(array, i, lastSmallerThenPivot--);
				while (lastSmallerThenPivot > from && array[lastSmallerThenPivot] >= pivot)
					lastSmallerThenPivot--;
			}
		ArrayUtil.swap(array, from, lastSmallerThenPivot);
		return lastSmallerThenPivot;
	}
	
}
